package com.hainiu.cat.sort.write;

/**
 * create by biji.zhao on 2021/6/14
 */
public class CommonTest {

    public static void main(String[] args) {
        int[] a = {1, 3, 20, 9, 10, 30, 2, 6};
        sort(a, 0, a.length - 1);

        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }

        int[] b = {1, 2, 3, 6, 10, 30, 45, 60};
        System.out.println("=====================");
        System.out.println(twoFind(b, 0, b.length - 1, 30));
        System.out.println(twoFind(b, 0, b.length - 1, 1));
        System.out.println(twoFind(b, 0, b.length - 1, 6));
    }

    private static int twoFind(int [] data, int left, int right, int k) {
        int mid = (right - left) / 2 + left;
        if (data[mid] == k) {
            return mid;
        }
        if (left >= right) {
            return left;
        }
        if (data[mid] < k) {
            return twoFind(data, mid + 1, right, k);
        }
        return twoFind(data, left, mid, k);
    }

    // 快速排序法
    private static void sort(int [] data, int left, int right) {
        if (left >= right) {
            return;
        }
        int k = data[left];
        int i = left;
        int j = right;
        while (i < j) {
            // 找到第一个比他小的
            while (i < j && data[j] >= k) {
                j --;
            }
            // 找到第一个比他大的
            while (i < j && data[i] <= k) {
                i ++;
            }
            if (i < j) {
                swap(data, i, j);
            }
        }
        data[left] = data[i];
        data[i] = k;
        // 排序左边
        sort(data, left, i - 1);
        // 排序右边
        sort(data, i + 1, right);
    }

    private static void swap(int [] data, int o, int t) {
        int temp = data[o];
        data[o] = data[t];
        data[t] = temp;
    }
}
